#light

//Second crack at imlementing the directed graph.
//This time I want it to match the designs I have been
//leaning towards; specifically having a data core that you
//can map interfaces onto.
module CGraph.DG2
open CGraph.Generic;
open CGraph.Generic.Algorithms;
open CGraph.IO

type EdgeHandleList = System.Collections.Generic.List<EdgeHandle>
and Vertex = 
    val mutable IncomingEdgesOption : EdgeHandleList option
    val mutable OutgoingEdgesOption : EdgeHandleList option
    new() = { IncomingEdgesOption = None; OutgoingEdgesOption = None }
    member private s.EdgesSeq (edges:EdgeHandleList option) = 
        match edges with
            | Some edges -> edges :> EdgeHandle seq
            | None -> [] :> EdgeHandle seq
            
    member s.IncomingEdges = s.EdgesSeq s.IncomingEdgesOption
    member s.OutgoingEdges = s.EdgesSeq s.OutgoingEdgesOption
    member vert.IncEdgeList = 
        match vert.IncomingEdgesOption with
            | Some edges -> edges
            | None ->
                let edges =  new System.Collections.Generic.List<EdgeHandle>()
                vert.IncomingEdgesOption <- Some edges 
                edges
    member vert.OutEdgeList = 
        match vert.OutgoingEdgesOption with
            | Some edges -> edges
            | None ->
                let edges =  new System.Collections.Generic.List<EdgeHandle>()
                vert.OutgoingEdgesOption <- Some edges 
                edges
and VertexHandle = Vertex Handle
and Edge = 
    val IncomingVertex : VertexHandle
    val OutgoingVertex : VertexHandle
    new( inc, out ) = { IncomingVertex=inc; OutgoingVertex = out }
and EdgeHandle = Edge Handle

type VertexList = VertexHandle System.Collections.Generic.List
//This graph is built under the assumption that most vertexes will have very few connections.
//Depending on the average degree, using an actual system.collections.list would be more efficient.
//So far, however, for the schema and data graphs they tend to have a degree of zero or one for all
//but a few vertexes.
type DirectedGraphData = { HandleSystem:ObjectHandleSystem; Vertexes:VertexList }

let CreateDirectedGraphData incFun = 
    let system = CreateObjectHandleSystem incFun
    { HandleSystem=system; Vertexes=System.Collections.Generic.List() }
    
     
    
type IDirectedGraph =
    abstract Vertexes : VertexHandle seq
    abstract Edges : EdgeHandle seq
    
    abstract Size : int with get //count of edges
    abstract Order : int with get //count of vertexes
    abstract InDegree : VertexHandle -> int
    abstract OutDegree : VertexHandle -> int
    abstract IncomingEdges : vertex:VertexHandle -> EdgeHandle seq
    abstract OutgoingEdges : vertex:VertexHandle -> EdgeHandle seq
    abstract IncomingVertex : edge:EdgeHandle -> VertexHandle
    abstract OutgoingVertex : edge:EdgeHandle -> VertexHandle
    
    abstract Vertex : unit->VertexHandle
    abstract Edge : incoming:VertexHandle*outgoing:VertexHandle->EdgeHandle
    abstract AddVertex : vert:VertexHandle->unit
    abstract AddEdge : edge:EdgeHandle -> unit
    //Also removes any edges associated with said vertex.
    abstract RemoveVertex : vert:VertexHandle -> unit
    abstract RemoveEdge : edge:EdgeHandle -> unit
    
let CreateDirectedGraph (data:DirectedGraphData) = 
    let GetOrCreateObjHandle = data.HandleSystem.GetOrCreateObjHandle
    let GetHandleObj = data.HandleSystem.GetHandleObj
    let ToHandle value = data.HandleSystem.ToHandle value
    let FromHandle hdl = data.HandleSystem.FromHandle hdl
    let EdgesSeq (edges:EdgeHandleList option) = 
        match edges with
            | Some edges -> edges :> EdgeHandle seq
            | None -> [] :> EdgeHandle seq
    let IncEdges (vert:Vertex) = vert.IncEdgeList
    let OutEdges (vert:Vertex) = vert.OutEdgeList
    
    { new IDirectedGraph with
        member s.Vertexes = data.Vertexes |> Seq.map(fun entry -> entry )
        member s.Edges = data.Vertexes |> Seq.map( fun entry -> (s.OutgoingEdges entry) ) |> Seq.concat
        member s.Size = Seq.length(s.Edges)
        member s.Order = data.Vertexes.Count
        member s.InDegree hdl = Seq.length <| s.IncomingEdges hdl 
        member s.OutDegree hdl = Seq.length <| s.OutgoingEdges hdl
        member s.IncomingEdges hdl = (FromHandle hdl).IncomingEdges
        member s.OutgoingEdges hdl = (FromHandle hdl).OutgoingEdges
        member s.IncomingVertex hdl = (FromHandle hdl).IncomingVertex
        member s.OutgoingVertex hdl = (FromHandle hdl).OutgoingVertex
        member s.Vertex() = 
            let retval = ToHandle (Vertex())
            s.AddVertex retval
            retval
        member s.AddVertex hdl =
            let vert = FromHandle hdl
            data.Vertexes.Add hdl
            
        member s.Edge(inc,out) =
            let edge = ToHandle (Edge(inc,out))
            s.AddEdge edge
            edge
            
        member s.AddEdge hdl =
            let edge = FromHandle hdl
            let inc = FromHandle edge.IncomingVertex
            let out = FromHandle edge.OutgoingVertex
            (OutEdges inc).Add hdl
            (IncEdges out).Add hdl
            
        member s.RemoveVertex hdl = 
            let vtx = FromHandle hdl
            System.Collections.Generic.List(vtx.IncomingEdges) |> Seq.iter( fun item -> s.RemoveEdge item )
            System.Collections.Generic.List(vtx.OutgoingEdges) |> Seq.iter( fun item -> s.RemoveEdge item )
            let entry = data.HandleSystem.HandleIndex.Items.[hdl.Handle]
            data.HandleSystem.ObjectMap.Remove entry |> ignore
            
        member s.RemoveEdge hdl =
            let edge = FromHandle hdl
            let incVert = FromHandle edge.IncomingVertex
            let outVert = FromHandle edge.OutgoingVertex
            (OutEdges incVert).Remove hdl |> ignore
            (IncEdges outVert).Remove hdl |> ignore
            let entry = data.HandleSystem.HandleIndex.Items.[hdl.Handle]
            data.HandleSystem.ObjectMap.Remove entry |> ignore
      }
      
      
/// Callbacks contain enough information to put the system exactly
/// back the way it was when the event happened.
/// Edge callback, index in IncomingVertex.OutgoingHandles
/// Edge callback, index in OutgoingVertex.IncomingHandles
type EdgeCallback = delegate of edge:EdgeHandle*incomingIndex:int*outgoingIndex:int->unit
type VertexCallback = delegate of vert:VertexHandle*vertIndex:int->unit

let CreateEventGraph (src:IDirectedGraph) (data:DirectedGraphData) (edgeAdded:EdgeCallback) (edgeRemoved:EdgeCallback) 
                        (vertAdded:VertexCallback) (vertRemoved:VertexCallback) = 
    let FromHandle hdl = data.HandleSystem.FromHandle hdl
    let ToHandle item = data.HandleSystem.ToHandle item
    { new IDirectedGraph with
        member s.Vertexes = src.Vertexes
        member s.Edges = src.Edges
        member s.Size = src.Size
        member s.Order = src.Order
        member s.InDegree hdl = src.InDegree hdl
        member s.OutDegree hdl = src.OutDegree hdl
        member s.IncomingEdges hdl = src.IncomingEdges hdl
        member s.OutgoingEdges hdl = src.OutgoingEdges hdl
        member s.IncomingVertex hdl = src.IncomingVertex hdl
        member s.OutgoingVertex hdl = src.OutgoingVertex hdl
        
        member s.Vertex() = 
            let vindex = data.Vertexes.Count
            let retval = s.Vertex()
            vertAdded.Invoke (retval,vindex)
            retval
        member s.AddVertex hdl =
            let vindex = data.Vertexes.Count
            src.AddVertex hdl
            vertAdded.Invoke (hdl,vindex)
            
        member s.Edge(inc,out) =
            let incCount = (FromHandle out).IncEdgeList.Count
            let outCount = (FromHandle inc).OutEdgeList.Count
            let edge = src.Edge(inc,out)
            edgeAdded.Invoke (edge,outCount,incCount)
            edge
            
        member s.AddEdge hdl =
            let inc = s.IncomingVertex hdl
            let out  = s.OutgoingVertex hdl
            let incCount = (FromHandle out).IncEdgeList.Count
            let outCount = (FromHandle inc).OutEdgeList.Count
            src.AddEdge hdl
            edgeAdded.Invoke (hdl,outCount,incCount)
            
        member s.RemoveVertex hdl =
            let vtx = FromHandle hdl
            System.Collections.Generic.List(vtx.IncomingEdges)
            |> Seq.iter( fun edge -> s.RemoveEdge edge )
            System.Collections.Generic.List(vtx.OutgoingEdges)
            |> Seq.iter( fun edge -> s.RemoveEdge edge )
            let vindex = data.Vertexes.IndexOf hdl
            src.RemoveVertex hdl
            vertRemoved.Invoke (hdl,vindex)
            
        member s.RemoveEdge hdl =
            let edge = FromHandle hdl
            let inc = FromHandle edge.IncomingVertex
            let out = FromHandle edge.OutgoingVertex
            let incIdx = inc.OutEdgeList.IndexOf hdl
            let outIdx = out.IncEdgeList.IndexOf hdl
            s.RemoveEdge hdl
            edgeRemoved.Invoke (hdl,incIdx,outIdx)
    }
      
      
type IntList = System.Collections.Generic.List<int>
      
//Writes vertex specific information.  Hopefully, all you need
//are integers.
type VertexWriter = Vertex -> (int->unit)-> unit
type EdgeWriter = Edge -> (int->unit) -> unit
      
let WriteDirectedGraphData (data:DirectedGraphData) (stream:IDataWriter) (vwrite:VertexWriter) (ewrite:EdgeWriter) =
    let GetOrCreateObjHandle = data.HandleSystem.GetOrCreateObjHandle
    let GetHandleObj = data.HandleSystem.GetHandleObj
    let ToHandle value = data.HandleSystem.ToHandle value
    let FromHandle hdl = data.HandleSystem.FromHandle hdl
    let vertexes = System.Collections.Generic.List<int>()
    let edgeDefs = System.Collections.Generic.List<int>()
    let edges = System.Collections.Generic.List<int>()
    //Simply write out the vertexes.
    data.Vertexes
    |> Seq.iter (fun vert ->
        let item = FromHandle vert
        vertexes.Add vert.Handle
        vwrite item vertexes.Add )
        
    data.Vertexes 
    |> Seq.iter( fun vert ->
        let item = FromHandle vert
        item.IncomingEdges
        |> Seq.iter( fun edge ->
            let realEdge = FromHandle edge
            edgeDefs.Add edge.Handle
            edgeDefs.Add realEdge.IncomingVertex.Handle
            edgeDefs.Add realEdge.OutgoingVertex.Handle
            ewrite realEdge edgeDefs.Add ) )
            
    
    let WriteEdgeList (vedges:EdgeHandle seq) =
        edges.Add (Seq.length vedges)
        vedges |> Seq.iter (fun edge -> edges.Add edge.Handle )
            
    data.Vertexes
    |> Seq.iter( fun vert ->
        let item = FromHandle vert
        WriteEdgeList item.OutgoingEdges
        WriteEdgeList item.IncomingEdges )
        
    stream.Ints <| vertexes.ToArray()
    stream.Ints <| edgeDefs.ToArray()
    stream.Ints <| edges.ToArray()
            
//These are expected to add the appropriate items
//to the handle collection, the reading function does
//not do this.  This is because the items will most likely
//be derived classes from Vertex and Edge, but not actually
//vertex or edge.
type VertexAccess = int->(unit->int)->Vertex
type EdgeAccess = int->VertexHandle->VertexHandle->(unit->int) -> Edge
            
//Reading and writing the graph does not preserve edge order.
let ReadDirectedGraphData (stream:IDataReader) (vertAccess:VertexAccess) (edgeAccess:EdgeAccess) =
    let vertexes = stream.Ints().GetEnumerator()
    let edgeDefs = stream.Ints().GetEnumerator()
    let edges = stream.Ints().GetEnumerator()
    let next (arg:'a System.Collections.Generic.IEnumerator) = 
        let test = arg.MoveNext()
        match test with
            | true -> arg.Current
            | false -> failwith "Ran out of data"
            
    let nextV() = next vertexes
    let nextE() = next edges
    let nextED() = next edgeDefs
    let vmap = System.Collections.Generic.Dictionary<int,Vertex>()
    let retval = System.Collections.Generic.List<int*Vertex>()
    
    let toVH arg = Handle<Vertex>(arg)
    let toEH arg = Handle<Edge>(arg)
    while( vertexes.MoveNext() ) do
        let vhandle = vertexes.Current
        let vert = vertAccess vhandle nextV
        vmap.Add(vhandle,vert)
        retval.Add((vhandle,vert))
        
    while edgeDefs.MoveNext() do
        let ehandle = edgeDefs.Current
        let inV = nextED()
        let outV = nextED()
        edgeAccess ehandle (toVH inV) (toVH outV) nextED |> ignore
        
    let ReadEdgeList (vtx:unit->EdgeHandle System.Collections.Generic.List) = 
        let ecount = nextE()
        if ecount <> 0 
            then 
                let vtxList = vtx()
                let edges = 
                    seq {
                        for idx in 1..ecount do
                            yield toEH <| nextE()
                    }
                vtxList.AddRange edges
    retval
    |> Seq.map( fun (hdl,vtx) ->
        ReadEdgeList <| fun() -> vtx.OutEdgeList
        ReadEdgeList <| fun() -> vtx.IncEdgeList
        (hdl,vtx))
    